#include <vector>
using std::vector;

//山峰数组，右侧更大时删去左侧区间

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0;
        int right = arr.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1])
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
};

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 */

 class MountainArray {
   public:
     int get(int index);
     int length();
 };

 //山峰数组两次二分法查值

class Solution {
    int search(int target, MountainArray &mountainArr, int left, int right, int sign) {
        target = sign * target;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int num = sign * mountainArr.get(mid);
            if (num == target)
                return mid;
            else if (num < target)
                left = mid + 1;
            else 
                right = mid - 1;
        }
        return -1;
    }

public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int left = 0;
        int right = mountainArr.length() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1))
                left = mid + 1;
            else 
                right = mid;
        }
        int peak = left;
        int result = search(target, mountainArr, 0, peak, 1);
        if (result == -1)
            result = search(target, mountainArr, peak + 1, mountainArr.length() - 1, -1);
        return result;
    }
};